// Package day_01_base_sort 34_find_first_last_index
// @Title day_01_base_sort
// @Description  在排序数组中查找元素的第一个和最后一个位置
// @Author  == 琳琳也叫王木木 ==  2021/9/2 9:44
// @Create  2021/9/2 9:44
package day_01_base_sort

import (
	"fmt"
	"sort"
)

/**
	我们先求一个排序数组出现第一个元素的最左下标
核心思想，二分查找，
左边<右边 进循环
大于等于切右边
小于 切左边+1
返回左边
*/

func SearchFirstMinIndex(nums []int, target int) int {
	var ans = -1
	if nums == nil || len(nums) < 1 {
		return ans
	}
	left, right := 0, len(nums)
	for left < right {
		mid := left + (right-left)>>1
		fmt.Println(left, right, mid)
		if nums[mid] >= target {
			right = mid
		} else {
			left = mid + 1
		}
	}
	if nums[left] == target {
		return left
	}
	return -1
}

// SearchFirstMaxIndex 获取最大的下标
func SearchFirstMaxIndex(nums []int, target int) int {
	var ans = -1
	if nums == nil || len(nums) < 1 {
		return ans
	}
	left, right := 0, len(nums)
	for left < right {
		mid := left + (right-left)>>1
		fmt.Println(left, right, mid)
		if nums[mid] <= target {
			left = mid
		} else {
			right = mid - 1
		}
	}
	return right
}

/**
思路, 因为是有序数组，所以可以使用二分法
*/

// SearchRange 这一版还有问题，如果没有数据的话，还是能查到
func SearchRange(nums []int, target int) []int {
	if nums == nil || len(nums) < 1 {
		return []int{-1, -1}
	}
	ans := make([]int, 0)
	left, right := 0, len(nums)
	for left < right {
		mid := left + (right-left)>>1
		if nums[mid] >= target {
			right = mid
		} else {
			left = mid + 1
		}
	}
	if nums[left] == target {
		ans = append(ans, left)
	} else {
		ans = append(ans, -1)
	}
	left, right = 0, len(nums)
	for left < right {
		mid := left + (right-left)>>1
		if nums[mid] <= target {
			left = mid
		} else {
			right = mid - 1
		}
	}
	if nums[right] == target {
		ans = append(ans, right)
	} else {
		ans = append(ans, -1)
	}
	return ans
}

// SearchRangeNice 这是最优解版本
func SearchRangeNice(nums []int, target int) []int {
	leftmost := sort.SearchInts(nums, target)
	if leftmost == len(nums) || nums[leftmost] != target {
		return []int{-1, -1}
	}
	rightmost := sort.SearchInts(nums, target+1) - 1
	return []int{leftmost, rightmost}
}
